﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using QuickGraph;

namespace DeadlockDetection
{
    public class Algorithms
    {
        private enum Colors { White, Grey, Black };
        Colors[] color;
        int[] previous;

        public List<int> Banker(Processes processes, Resources resources)
        {
            int n = processes.Length;
            int m = resources.Length;

            int deadlockedProcessesLength = 0;
            bool searchExhausted;
            int iterator;

            bool[] finish = new bool[n];

            List<int> deadlockedProcessesIds = new List<int>();
            int[] work = new int[m];

            for (int i = 0; i < m; i++)
            {
                work[i] = resources[i].availableInstances;
            }

            for (int i = 0; i < n; i++)
            {
                if (finish[i] == false)
                {
                    if (firstLesserOrEqual(processes[i].resourcesRequested, work))
                    {
                        addToFirstVector(work, processes[i].resourcesAllocated);
                        finish[i] = true;
                    }
                    else
                    {
                        deadlockedProcessesIds.Add(i);
                        deadlockedProcessesLength++;
                    }
                }
            }

            searchExhausted = false;
            while (!searchExhausted)
            {
                searchExhausted = true;
                iterator = 0;
                foreach (int i in deadlockedProcessesIds)
                {
                    if (finish[i] == false)
                    {
                        if (firstLesserOrEqual(processes[i].resourcesRequested, work))
                        {
                            addToFirstVector(work, processes[i].resourcesAllocated);
                            finish[i] = true;
                            deadlockedProcessesIds.RemoveAt(iterator);
                            deadlockedProcessesLength--;
                            searchExhausted = false;
                        }
                    }
                    iterator++;
                }
            }
            
            return deadlockedProcessesIds;
        }

        public bool Graphs(BidirectionalGraph<object, IEdge<object>> graph, int numberOfProcesses)
        {
            color = new Colors[numberOfProcesses];
            previous = new int[numberOfProcesses];
            bool isCyclic = false;

            foreach (string vertex in graph.Vertices)
            {
                int id = Convert.ToInt32(vertex.Remove(0, 1));
                color[id] = Colors.White;
                previous[id] = -1;
            }

            foreach (string vertex in graph.Vertices)
            { 
                int id = Convert.ToInt32(vertex.Remove(0, 1));
                if (color[id] == Colors.White)
                {
                    isCyclic = dfsVisit(graph, vertex, id);
                    if (isCyclic) return true;
                }
            }

            return isCyclic;
        }


        private bool dfsVisit(BidirectionalGraph<object, IEdge<object>> graph, string vertex, int id)
        {
            bool isCyclic = false;
            
            color[id] = Colors.Grey;
            IEnumerable<IEdge<object>> edge;
            graph.TryGetOutEdges(vertex, out edge);
            foreach (Edge<object> e in edge)
            {
                string vertex2 = (string)e.GetOtherVertex<object, Edge<object>>(vertex);
                int id2 = Convert.ToInt32(vertex2.Remove(0, 1));
                if (color[id2] == Colors.White)
                {
                    previous[id2] = id;
                    isCyclic = dfsVisit(graph, vertex2, id2);
                    if (isCyclic) return true;
                }
                else if (color[id2] == Colors.Grey)
                {
                    return true;
                }
            }
            color[id] = Colors.Black;

            return isCyclic;
        }

        private bool firstLesserOrEqual(int[] vector1, int[] vector2)
        {
            int m = vector1.Length;
            for (int i = 0; i < m; i++)
            {
                if (vector1[i] > vector2[i])
                    return false;
            }

            return true;
        }

        private int[] addVectors(int[] vector1, int[] vector2)
        {
            int length = vector1.Length;
            int[] resultVector = new int[length];

            for (int i = 0; i < length; i++)
            {
                resultVector[i] = vector1[i] + vector2[i];
            }

            return resultVector;
        }

        private void addToFirstVector(int[] vector1, int[] vector2)
        {
            int length = vector1.Length;

            for (int i = 0; i < length; i++)
            {
                vector1[i] = vector1[i] + vector2[i];
            }
        }
    }
}
